package com.person.leetcode.editor.cn;

import java.util.Arrays;

/**
 * 1051.高度检查器
 * 2022-06-13 10:14:55
 **/
public class Sequence_1051_HeightChecker {
    public static void main(String[] args) {
        Solution solution = new Sequence_1051_HeightChecker().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int heightChecker(int[] heights) {
//            int m = Arrays.stream(heights).max().getAsInt();
//            int[] cnt = new int[m + 1];

            int m = 100;
            int[] cnt = new int[m + 1];
            for (int h : heights) {
                ++cnt[h];
            }

            int idx = 0, ans = 0;
            for (int value = 1; value <= m; ++value) {
                for (int j = 1; j <= cnt[value]; ++j) {
                    if (heights[idx] != value) {
                        ++ans;
                    }
                    ++idx;
                }
            }
            return ans;
        }
    }


//leetcode submit region end(Prohibit modification and deletion)

}